package com.salim.leetcode.$29;

public class DivideTwoIntegers {
    //纯减法 超时
    public int divide(int dividend, int divisor) {
        if(dividend==0){
            return 0;
        }
        boolean positive = true;
        if((dividend>=0& divisor>0) || (dividend<0&divisor<0)){
            positive = true;
        }else if((dividend>=0& divisor<0) || (dividend<0 & divisor>0)){
            positive = false;
        }
        long absDividend = Math.abs((long)dividend);
        long absDivisor = Math.abs((long)divisor);
        long result = 0;
        while (absDividend>=absDivisor){
            result++;
            absDividend-=absDivisor;
        }
        if (result > Integer.MAX_VALUE){
            return positive?Integer.MAX_VALUE:Integer.MIN_VALUE;
        }else{
            return positive?(int)result:(int)-result;
        }
    }

    //二分查找
    public int divide2(int dividend, int divisor) {
        boolean positive = true;
        if((dividend>=0& divisor>0) || (dividend<0&divisor<0)){
            positive = true;
        }else if((dividend>=0& divisor<0) || (dividend<0 & divisor>0)){
            positive = false;
        }
        long ldividend = Math.abs((long) dividend);
        long ldivisor = Math.abs((long) divisor);

        //Take care the edge cases.
        if (ldivisor == 0) return Integer.MAX_VALUE;
        if ((ldividend == 0) || (ldividend < ldivisor))	return 0;

        long lans = ldivide(ldividend, ldivisor);

        int ans;
        if (lans > Integer.MAX_VALUE){ //Handle overflow.
            ans = positive? Integer.MAX_VALUE : Integer.MIN_VALUE;
        } else {
            ans = positive?(int)lans:(int)-lans;
        }
        return ans;
    }

    private long ldivide(long ldividend, long ldivisor) {
        // Recursion exit condition
        if (ldividend < ldivisor) return 0;

        //  Find the largest multiple so that (divisor * multiple <= dividend),
        //  whereas we are moving with stride 1, 2, 4, 8, 16...2^n for performance reason.
        //  Think this as a binary search.
        long sum = ldivisor;
        long multiple = 1;
        while ((sum+sum) <= ldividend) {
            sum += sum;
            multiple += multiple;
        }
        //Look for additional value for the multiple from the reminder (dividend - sum) recursively.
        return multiple + ldivide(ldividend - sum, ldivisor);
    }

    public static void main(String[] args){
        DivideTwoIntegers divideTwoIntegers = new DivideTwoIntegers();
        System.out.println(divideTwoIntegers.divide(Integer.MIN_VALUE,2));
    }
}
